26. Remove Duplicates from Sorted Array

今天我們一起挑戰leetcode第26題Remove Duplicates from Sorted Array！

題目

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

這個題目敘述真的是有點長，我們簡單來說的話，其實這題目就是會給我們一個排序過的陣列，希望我們把陣列重複的元素拿掉。但這題是不用回傳陣列的，只要在原本的陣列把移除重複元素後的陣列，所有元素往陣列頭的方向排，然後再回傳一整數來表示在陣列中有幾個不重複的數字。

這題有額外要求，不可以另外新增O(n)的空間，必須在複雜度O(1)達成，且題目也不會管不重複元素後的元素是放麼東西，也就是他只會檢查陣列中的前K（不重複元素個數）個。

Forloop

我們可以利用題目本身的陣列一定是排序過的特性來做這道題目，額外利用兩個變數來記住現在要放的位置（count）和現在已經看過的值，概念上是只要我們沒有看過的東西我們就把他放到陣列index為0的位置，而此時count就加一，下次再看到新的東西時就會放到index為1的位置。這邊的放到某個位置是指直接改變那個位置的值不是插入，如此一來，只需要遍歷迴圈一遍就能成功達到題目的要求。在程式碼中我也會用comment來說明概念，如果還是不太清楚可以直接看一下code。

以下是python3的程式碼

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0  # 空陣列就回傳0
        compare = nums[0] # 把第一個元素當作基準
        count = 1  # 因為非空陣列至少為一
        for i in range(1, len(nums)):  # 從index1開始
            if nums[i] != compare:   # 如果比對到不同的
                nums[count] = nums[i]  # 就放對對應的位置
                compare = nums[i]  # 更改比對基準
                count += 1  # 計數器加一
        return count

以下是C++的程式碼

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int count=1;
        int compare=nums[0];
        for(int i=1;i<nums.size();i++){
            if(nums[i] != compare){
                nums[count] = nums[i];
                compare = nums[i];
                count++;
            }
        }
        return count;
    }
};